package cn.fxzhang.leetcode.no11;


/**
 * 1143. 最长公共子序列
 * 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
 *  一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
 * 输入：text1 = "abcde", text2 = "ace"
 * 输出：3
 * 解释：最长公共子序列是 "ace" ，它的长度为 3 。
 *
 * 类型：动态规划
 * 题解：f[i][j] = Math.max(Math.max(f[i][j-1], f[i-1][j]), f[i-1][j-1]) + (s1[i]==s1[j]?1:0))
 * 时间复杂度：O(N*M)
 * 空间复杂度：O(N*M)
 *
 * 提交记录(1/2)：
 * 执行用时: 19 ms, 击败了10.05%
 * 内存消耗: 42.5 MB, 击败了11.05%
 *
 * 【中等】通过次数100,216提交次数161,677
 * @author 张晓帆
 * @date 2021/04/03
 */
public class P1143_Longest_Common_Subsequence {

    public int longestCommonSubsequence(String s1, String s2) {
        int[][] f = new int[s1.length()][s2.length()];
        // 边界处理
        f[0][0] = s1.charAt(0) == s2.charAt(0)? 1: 0;
        for (int i = 1; i < s2.length(); i++){
            if (s1.charAt(0) == s2.charAt(i)){
                f[0][i] = 1;
            } else {
                f[0][i] = f[0][i-1];
             }
        }
        for (int i = 1; i < s1.length(); i++){
            if (s2.charAt(0) == s1.charAt(i)){
                f[i][0] = 1;
            } else {
                f[i][0] = f[i-1][0];
            }
        }
        for (int i = 1; i < s1.length(); i++){
            for (int j = 1; j < s2.length(); j++){
                f[i][j] = Math.max(f[i][j-1], f[i-1][j]);
                if (s1.charAt(i) == s2.charAt(j)){
                    f[i][j] = f[i-1][j-1] + 1;
                }
            }
        }
        return f[s1.length()-1][s2.length()-1];
    }

}
